<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">

<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<link rel="stylesheet" type="text/css" href="style.css" media="all" />
<title>RSA</title>
</head>

<body>

<center>
<div style="width: 70%; position:absolute; left:10%; top:0%; z-index:1">
<br />
<div class="tabArea" align="center">
  <a class="tab" href="example.php">Example</a>
      <a class="tab" href="about.html">About RSA</a> 
      <a class="tab" href="DigitalSignature.html">About Digital Signature</a> 
  </div>

<div class="Paragraph">

<h2>RSA</h2><br />

<div class="img-shadow">
<img src="images/thumb.jpg" alt="Khaled Al-Sham'aa" border="0" width="194" height="241" />
</div>

      <span class="FirstChar">T</span>his algorithm is based on the difficulty 
      of factorizing large numbers that have 2 and only 2 factors (Prime numbers). 
      The system works on a public and private key system. The public key is made 
      available to everyone. With this key a user can encrypt data but cannot 
      decrypt it, the only person who can decrypt it is the one who possesses the 
      private key. It is theoretically possible but extremely difficult to generate 
      the private key from the public key, this makes the RSA algorithm a very 
      popular choice in data encryption.<br /><br />
      <h2>Key Generation</h2>      
      <ul>
        <span class="Quote"> Its security comes from the computational difficulty 
        of factoring large numbers. To be secure, very large numbers must be used for p 
        and q - 100 decimal digits at the very least. </span>
      </ul>
      <p><strong>1) Generate two large prime numbers, p and q</strong><br />
        To make the example easy to follow I am going to use small numbers, but 
        this is not secure. To find random primes, we start at a random number 
        and go up ascending odd numbers until we find a prime. Lets have: <br />
        <blockquote>
        p = 7<br />
        q = 19<br />
        </blockquote>
        <strong>2) Let n = pq</strong><br />
        <blockquote>
        n = 7 * 19<br />
        = 133<br />
        </blockquote>
        <strong>3) Let m = (p - 1)(q - 1)</strong><br />
        <blockquote>
        m = (7 - 1)(19 - 1)<br />
        = 6 * 18<br />
        = 108<br />
        </blockquote>
        <strong>4) Choose a small number, e coprime to m</strong><br />
        e coprime to m, means that the largest number that can exactly divide 
        both e and m (their greatest common divisor, or gcd) is 1. Euclid's algorithm 
        is used to find the gcd of two numbers, but the details are omitted here.<br />
        <blockquote>
        e = 2 =&gt; gcd(e, 108) = 2 (no)<br />
        e = 3 =&gt; gcd(e, 108) = 3 (no)<br />
        e = 4 =&gt; gcd(e, 108) = 4 (no)<br />
        e = 5 =&gt; gcd(e, 108) = 1 (yes!) <br />
        </blockquote>
        <strong>5) Find d, such that de % m = 1</strong><br />
        This is equivalent to finding d which satisfies de = 1 + nm where n is 
        any integer. We can rewrite this as d = (1 + nm) / e. Now we work through 
        values of n until an integer solution for e is found:<br />
        <blockquote>
        n = 0 =&gt; d = 1 / 5 (no)<br />
        n = 1 =&gt; d = 109 / 5 (no)<br />
        n = 2 =&gt; d = 217 / 5 (no)<br />
        n = 3 =&gt; d = 325 / 5 <br />
        = 65 (yes!)<br />
        </blockquote>
        To do this with big numbers, a more sophisticated algorithm called extended 
        Euclid must be used.<br />
        <br />
        <strong>Public Key</strong><br />
        <blockquote>
        n = 133<br />
        e = 5<br />
        </blockquote>
        <br />
        <strong> Private Key (Secret Key</strong>)<br />
        <blockquote>
        n = 133<br />
        d = 65</p>
        </blockquote>
      <h2>Communication</h2>
        <strong>Encryption</strong><br />
        The message must be a number less than the smaller of p and q. However, 
        at this point we don't know p or q, so in practice a lower bound on p 
        and q must be published. This can be somewhat below their true value and 
        so isn't a major security concern. For this example, lets use the message 
        &quot;6&quot;.<br />
        <blockquote>
        C = Pe % n<br />
        = 65 % 133<br />
        = 7776 % 133<br />
        = 62<br />
        </blockquote>
        <strong>Decryption</strong><br />
        This works very much like encryption, but involves a larger exponation, 
        which is broken down into several steps.<br />
        <blockquote>
        P = Cd % n<br />
        = 6265 % 133<br />
        = 62 * 6264 % 133<br />
        = 62 * (622)32 % 133<br />
        = 62 * 384432 % 133<br />
        = 62 * (3844 % 133)32 % 133<br />
        = 62 * 12032 % 133<br />
        </blockquote>
        We now repeat the sequence of operations that reduced 6265 to 12032 to 
        reduce the exponent down to 1.<br />
        <blockquote>
        = 62 * 3616 % 133<br />
        = 62 * 998 % 133<br />
        = 62 * 924 % 133<br />
        = 62 * 852 % 133<br />
        = 62 * 43 % 133<br />
        = 2666 % 133<br />
        = 6 <br />
        </blockquote>
        And that matches the plaintext we put in at the beginning, so the algorithm 
        worked!<br />
        <br />
        <br />
        <br />
        <br />
      </p>
    </div>
<br />
</div>
</center>
          <script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
          </script>
          <script type="text/javascript">
          _uacct = "UA-1268287-1";
          urchinTracker();
          </script>
</body>
</html>
 
